package com.coder.algorithm.leetcode;

public class l_0633 {

    public static void main(String[] args) {
        Solution solution = new Solution();

        long start = System.currentTimeMillis();
        System.out.println(solution.judgeSquareSum1(999999999));
        long cur = System.currentTimeMillis();
        System.out.println(cur-start);

        start = System.currentTimeMillis();
        System.out.println(solution.judgeSquareSum2(999999999));
        cur = System.currentTimeMillis();
        System.out.println(cur-start);
    }


    static class Solution {
        public boolean judgeSquareSum1(int c) {
            for (long a = 0; a * a <= c; a++) {
                double b = Math.sqrt(c - a * a);
                if (b == (int) b) {
                    return true;
                }
            }
            return false;
        }

        public boolean judgeSquareSum2(int c) {
            long left = 0;
            long right = (long) Math.sqrt(c);
            while (left <= right) {
                long sum = left * left + right * right;
                if (sum == c) {
                    return true;
                } else if (sum > c) {
                    right--;
                } else {
                    left++;
                }
            }
            return false;
        }
    }
}
